package com.linyaonan.leetcode.medium._2080;

import java.util.Arrays;

/**
 * 请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
 *
 * 子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
 *
 * 请你实现 RangeFreqQuery 类：
 *
 * RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
 * int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。
 * 一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：
 * ["RangeFreqQuery", "query", "query"]
 * [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
 * 输出：
 * [null, 1, 2]
 *
 * 解释：
 * RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
 * rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
 * rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。
 *
 *
 * 提示：
 *
 * 1 <= arr.length <= 10^5
 * 1 <= arr[i], value <= 10^4
 * 0 <= left <= right < arr.length
 * 调用 query 不超过 10^5 次。
 *
 * @author: Lin
 * @date: 2024/12/3
 */
public class RangeFreqQueryBak {

    int[] org;

    /**
     * 该写法会超时
     * @param arr
     */
    public RangeFreqQueryBak(int[] arr) {
        org = arr;
    }

    public int query(int left, int right, int value) {
        int[] temp = new int[right - left + 1];
        System.arraycopy(org, left, temp, 0, temp.length);

        Arrays.sort(temp);

        // 边界
        if(temp[0] > value || temp[temp.length - 1] < value) {
            return 0;
        }
        int ll = -1;
        // 最左匹配
        {
            int l = 0;
            int r = temp.length - 1;
            while (l <= r) {
                int m = (l + r) >>> 1;
                int tempVal = temp[m];
                if (tempVal == value) {
                    ll = m;
                    r = m - 1;
                } else if (tempVal < value) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
        }

        if (ll == -1) {
            return 0;
        }
        int rr = ll;
        // 最右匹配
        {
            int l = ll;
            int r = temp.length - 1;
            while (l <= r) {
                int m = (l + r) >>> 1;
                int tempVal = temp[m];
                if (tempVal == value) {
                    rr = m;
                    l = m + 1;
                } else if (tempVal < value) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
        }

        return rr - ll + 1;
    }
}
